The present invention is related to Huffman decoding.
As is well-known, Huffman coding is a popular variable length statistical encoding scheme. As is also well-known, Huffman code generation relies on statistical probabilities for each individual symbol. See, for example, D. A. Huffman, “A Method for the Reconstruction of Minimum-Redundancy Codes” Proceedings of the IRE, Volume 40, No. 9, pages 1098-1101, 1952. A traditional table lookup based encoding scheme is widely used for Huffman encoding due, at least in part, to its efficiency and relative ease of implementation. However, table searching based decoding is typically inefficient in both software and hardware implementations. This is especially the case when the number of entries in a table is reasonably high, as is typical for practical applications. Another approach employed for Huffman decoding is the creation of a Huffman tree which employs a “tree traversing technique.” However, this decoding technique also has disadvantages. This particular technique is bit sequential, and introduces extra “overhead” both in terms of memory allocation and the execution of computations for the Huffman tree generation process and for the decoding process.